package com.hyb.algorithm.data.struct.tree;

import com.hyb.algorithm.data.struct.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: ybhu
 * @create: 2023/12/24 21:45
 */
public class PathSum {

    public static void main(String[] args) {

        TreeNode root =new TreeNode(10);
        root.left=new TreeNode(5);
        root.left.left=new TreeNode(3);
        root.left.left.left=new TreeNode(3);

        root.left.right=new TreeNode(2);
        root.left.right.right=new TreeNode(1);

        root.left.left.right=new TreeNode(-2);

        root.right=new TreeNode(-3);
        root.right.right=new TreeNode(11);


        int res=  new Test().pathSum(root,8);

        System.out.println(res);

        //System.out.println(JSONObject.toJSON(res));
    }


    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        curr += root.val;

        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        return ret;
    }
}
